package problem.year2021.march;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
 * 提示：
 * 1 <= s.length <= 3 * 105
 * s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
 * s 表示一个有效的表达式
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/basic-calculator
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class March10 {
    public int calculate(String s) {
        Deque<Integer> stack = new LinkedList<Integer>();
        char preSign = '+';
        int num = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            if (Character.isDigit(s.charAt(i))) {
                num = num * 10 + s.charAt(i) - '0';
            }
            if (s.charAt(i) == '('){
                int left = 1;
                for (int j = i+1; j < n; ++j) {
                    if (s.charAt(j) == '(') {
                        left++;
                        continue;
                    }
                    if (s.charAt(j) == ')') {
                        left--;
                        if (left == 0){
                            num = calculate(s.substring(i+1,j));
                        }
                    }
                }
            }
            if (!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ' || i == n - 1) {
                switch (preSign) {
                    case '+':
                        stack.push(num);
                        break;
                    case '-':
                        stack.push(-num);
                        break;
                    case '*':
                        stack.push(stack.pop() * num);
                        break;
                    case '/':
                        stack.push(stack.pop() / num);
                }
                preSign = s.charAt(i);
                num = 0;
            }
        }
        int ans = 0;
        while (!stack.isEmpty()) {
            ans += stack.pop();
        }
        return ans;
    }

    /**
     * * 示例 1：
     * * 输入：s = "1 + 1"
     * * 输出：2
     * * 示例 2：
     * * 输入：s = " 2-1 + 2 "
     * * 输出：3
     * * 示例 3：
     * * 输入：s = "(1+(4+5+2)-3)+(6+8)"
     * * 输出：23
     *
     * @param args
     */
    public static void main(String[] args) {
        String s = "124456";
        System.out.println(s.substring(1, 3));
    }
}
